首页 > 试题广场 >

最大数

[编程题]最大数
  • 热度指数：37309 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为n的数组nums，数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出。

数据范围：，
进阶：时间复杂度 ，空间复杂度：
示例1

输入

[30,1]

输出

"301"
示例2

输入

[2,20,23,4,8]

输出

"8423220"
示例3

输入

[2]

输出

"2"
示例4

输入

[10]

输出

"10"

备注:
输出结果可能非常大，所以你需要返回一个字符串而不是整数。
算法知识视频讲解
添加回答
Python 3
danspace头像 danspace 
from functools import cmp_to_key
class Solution:
    def solve(self , nums: List[int]) -> str:
        # write code here   
        if nums.count(0) == len(nums):
            return '0'
        def comp(a,b):
            ab = int(str(a)+str(b))
            ba = int(str(b)+str(a))
            if ab < ba: return 1
            elif ab == ba: return 0
            else: return -1
        nums.sort(key = cmp_to_key(comp))
        res = ''.join(map(str, nums))
        if res == '':
            return '0'
        return res

发表于 2022-04-25 11:46:42 回复(0)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def solve(self , nums: List[int]) -> str:
        # write code here
        for j in range(len(nums)):
            for i in range(0,len(nums)-j-1):
                if int(str(nums[i])+str(nums[i+1]))<int(str(nums[i+1])+str(nums[i])):
                    nums[i],nums[i+1]=nums[i+1],nums[i]
        
        v=''
        for i in nums:
            if i!=0&nbs***bsp;v!='':
                v+=str(i)
                
        return v if v else '0'

发表于 2022-01-17 09:14:10 回复(0)
Python 3
_进击的牛牛头像 _进击的牛牛
#
# 最大数
# @param nums int整型一维数组 
# @return string字符串
#比较规则
class cmp(str):
    def __lt__(x, y):
        return x+y > y+x
class Solution:     
    def solve(self , nums ):
        # write code here
        #将整型的数字转化为字符串
        strs = [str(i) for i in nums]
        #排序
        strs = sorted(strs, key=cmp)
        if strs[0] == '0':return "0"
#这个地方需要注意如果第一个字符串已经是0了，那么直接输出0
        return "".join(strs)
发表于 2021-09-14 15:58:54 回复(0)
Python 3
VincentLau~头像 VincentLau~ 
from functools import cmp_to_key
class Solution:
    def solve(self , nums ):
        # write code here
        nums = map(str, nums)
        def cmp(x, y):
            return 1 if y+x > x+y else -1
        res = sorted(nums, key=cmp_to_key(cmp))
        return "".join(res if res[0]!='0' else '0')

发表于 2021-08-14 15:02:31 回复(0)
Python 3
Stephenling头像 Stephenling
#
# 最大数
# @param nums int整型一维数组 
# @return string字符串
#
class compare(str):
    def __lt__(x, y):
        return x+y > y+x
class Solution:
    def solve(self , nums ):
        # write code here
        if  nums[0]==0:
            return 0
        new_num=sorted(nums,key=compare)
        print(new_num)
        new_num=[str(i) for i in new_num]
        return "".join(new_num)
发表于 2021-08-08 23:32:07 回复(0)
Python 3
牛客782226559号头像 牛客782226559号
一个自定义规则的冒泡排序可以解决该题目
我们把列表里面的每个数字定义为元素
观察题目我们可以得出如下优先级规则：
  1. 列表里面每个元素中第一个数字最大的应该排前面
  2. 第一个数字都相同的情况下，元素长度越短，越应该排前面
  3. 第一个数字都相同，元素长度也相同的情况下，元素化为数字比较，越小的排在后面
只要符合上述条件的任意一个就发生交换
源码如下： 
#
# 最大数
# @param nums int整型一维数组 
# @return string字符串
#
class Solution:
    def solve(self , nums ):
        # write code here
        temp=-1
        floor=len(nums)-1
        
        st=list(map(str,nums))
        while floor>0:
            for i in range(floor):
                if st[i][0]<st[i+1][0]:
                    temp=st[i+1]
                    st[i+1]=st[i]
                    st[i]=temp
                elif st[i][0]==st[i+1][0] and len(st[i])>len(st[i+1]):
                    temp=st[i+1]
                    st[i+1]=st[i]
                    st[i]=temp
                elif st[i][0]==st[i+1][0] and len(st[i])==len(st[i+1]) and int(st[i])<int(st[i+1]):
                    temp=st[i+1]
                    st[i+1]=st[i]
                    st[i]=temp
                
            floor-=1
                
        set_st=set(st)#全部是0，则返回0 ‘[0,0,0]’--->0
        if len(set_st)==1 and '0' in set_st:
            return '0'
        
        return ''.join(st)


发表于 2021-07-25 23:08:02 回复(1)
Python 3
牛客515624113号头像 牛客515624113号 
class compare(str):
    def __lt__(x, y):
        return x+y > y+x
class Solution:
    def solve(self , nums ):
        # write code here
        if  nums[0]==0:
            return 0
        new_num=sorted(nums,key=compare)
        new_num=[str(i) for i in new_num]
        return "".join(new_num)


发表于 2021-07-14 17:02:17 回复(0)
提交观点

问题信息

排序
上传者：牛客332641号
难度：
7条回答 6970浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号